1832B - Maximum Sum - CodeForces Solution

// بسم الله الرحمن الرحيم
// 907
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#define             endl "\n"
#define             ll long long
#define             pii pair<int,int>
#define             pll pair<ll,ll>
#define             f(a) for(int i=0;i<a;i++)
#define             rf(a) for(int i=a-1;i>=0;i--)
#define             w  int t;cin>>t;while(t--)
#define             all(v) v.begin(),v.end()
#define             yes cout<<"YES"<<endl;
#define             no cout<<"NO"<<endl;
#define             prev2pn(x) pow(2,floor(log2(x)))
#define             RR iostream::sync_with_stdio(false);cin.tie(nullptr); \
                    cout.tie(nullptr);
#define             arrRange(a , l , r) int _##a[(r-l)+1]; int* a= _##a-l;
#define             ordered_set tree<pll, null_type,less<pll>, \
                    rb_tree_tag,tree_order_statistics_node_update>
#define             OO 0x3f3f3f3f3f3f3f3f
#define             pr(v) for(int i=0;i<v.size();i++)cout<<v[i]<<" ";
#define             ld long double
#define             fr first
#define             se second
#define             sz(s) (int)s.size()
#define             posmod(number,modular) ((number)%(modular)+(modular))%(modular)
#define             ones(x) __builtin_popcount(x)
const ll MOD=1e9+7;
const int N= 2e5+5;
const int K= 2e5+5;
const double EPS = 1e-6;
const double PI = 3.14159265;

using namespace std;
ll n,m,k;
ll lcm(ll a,ll b){
    return (a*b)/__gcd(a,b);
}

ll powr(ll b,ll p) {
    ll sum = 1;
    for (int i = 1; i <= p; ++i) {
        sum *= b;
    }
    return sum;
}
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
vector<int>adj[N];
bool vis[105][105];

ll fast(ll xx, ll nn) {
    ll result = 1;
    while (nn > 0) {
        if ((nn & 1) == 1) // y is odd
        {
            result = (result )%MOD * (xx )%MOD;
        }
        xx = (xx )%MOD * (xx )%MOD;
        nn = nn >> 1; // y=y/2;
    }
    return (result );
}

bool valid(int a,int b){
    return a<0||b<0||a>=n||b>=m;
}

void solve() {
    cin>>n>>m;
    deque<ll> arr(n),b(n),c(n),d(n);
    ll sum1=0,sum2=0,sum3=0,sum4=0;
    for (int i = 0; i < n; ++i) {
        cin>>arr[i];
    }
    sort(all(arr));
    ll pre[n+1],suff[n+1];
    memset(pre,0,sizeof pre);
    for (int i = 0; i <n ; ++i) {
        pre[i]=(i?pre[i-1]:0)+arr[i];
    }
    ll ans=0;
    for (int i = 0; i <=m ; ++i) {
        ll l=i*2,r=n-(m-i)-1;
        ans=max(ans,pre[r]-(l?pre[l-1]:0));
    }
    cout<<ans<<endl;
}
int main() {
    RR
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int q = 1,d=1;
    cin>>q;
    while (q--) {
        solve();
    }
    cerr << "Time elapsed: " << clock() / 1000 << " ms" << endl;
    return 0;
}